#include "nthUglyNumber.h"
int nthUglyNumber(int n) {
    if (n <= 1)
        return n;
    std::vector<int> dp = std::vector<int>(n + 1, 0);
    dp[1] = 1;
    int p2 = 1, p3 = 1, p5 = 1;
    for (int i = 2; i <= n; i++) {
        int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;

        dp[i] = std::min(std::min(dp[p2] * 2, dp[p3] * 3), dp[p5] * 5);
        if (dp[i] == num2)
            p2++;
        if (dp[i] == num3)
            p3++;
        if (dp[i] == num5)
            p5++;
    }
    return dp[n];
}
